package com.example.leetcode.DynamicProgramming;

/**
 *
 * 输入：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *    偷窃到的最高金额 = 1 + 3 = 4 。
 *
 *  状态定义：
 *  状态转移方程：
 *      偷窃第k间房屋，那么就不能偷窃第 k-1间房屋，偷窃总金额为前k-2间房屋的最高总金额与第k间房屋的金额之和。
 *      不偷窃第k间房屋，偷窃总金额为前 k-1间房屋的最高总金额。
 *      例如：3间房子，偷第三间，总金额 = 第三间 + 第一间
 *          偷第二间，总金额 = 第二间房屋之前的房屋的最高总金额
 *      f（n）= Math.max(f(k-1), f(k-2) + nums(n))
 *
 *
 *
 *  边界条件：
 *      f(1) = nums[0]
 *      f(2) = nums[0] 或 nums[1]
 * @Description TODO
 * @date 2021/6/25 16:34
 * @Author liuzhihui
 * @Version 1.0
 */
public class Solution_2_198 {
    public static void main(String[] args) {

//        int[] nums = new int[] {1,2,3,1};
        int[] nums = new int[] {2,7,9,3,1};

        int rob = rob(nums);
        System.out.println(rob);
    }

    public static int rob(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }

        // 状态定义
        int[] temp =new int[nums.length];

        // 边界条件
        temp[0] = nums[0];
        temp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            // 状态定义方程
            temp[i] = Math.max(temp[i - 1], temp[i - 2] + nums[i]);
        }

        return temp[nums.length - 1];
    }


}
